class Solution {
private:
    vector<vector<int>> match;
    vector<bool> vis;
    int num;
    void dfs(int index, int n){
        if(index > n){
            num++;
            return;
        }
        for(int i = 0; i < match[index].size(); i++){
            if(!vis[match[index][i]]){
                vis[match[index][i]] = true;
                dfs(index + 1, n);
                vis[match[index][i]] = false;
            }
        }
    }
public:
    int countArrangement(int n) {
        match.resize(n + 1); //resize不会有默认填充，push_back 的话会从下标 0 开始
        vis = vector<bool>(n + 1, false);
        num = 0;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(!(i % j) || !(j % i))match[i].push_back(j);
            }
        }
        dfs(1, n);
        return num;
    }
};


/**
 * 2021.8.16
 * 暴力回溯
 * 事先处理每个位置可以放置的数字，
 * 爆搜每个位置，当形成一个排列时答案++
 * 注意回溯时把修改过的标志还原。
 */